package com.practice.graph;

import java.util.ArrayList;
import java.util.HashSet;

public class ConnectedComponent {
	/**
	 * Given 0-1 matrix, returns the max 1 component size.
	 */
	public int maxComponent(int[][] matrix) {
		int M = matrix.length;
		int N = matrix[0].length;
		int[][] label = new int[M][N];
		int K = 1;
		ArrayList<Integer> count = new ArrayList<Integer>();
		count.add(0);	// for border
		ArrayList<HashSet> sets = new ArrayList<HashSet>();
		
		// Scan
		for (int i=0; i<M; i++) {
			for (int j=0; j<N; j++) {
				if (matrix[i][j] == 0) continue;
				
				int west = j>0? label[i][j-1] : 0;
				int north = i>0? label[i-1][j] : 0;
				
				if (west==0 && north==0) {
					label[i][j] = K;
					count.add(1);
					
					HashSet<Integer> set = new HashSet<Integer>();
					set.add(K);
					sets.add(set);
					
					K++;
				}
				else if (west == 0) {
					label[i][j] = north;
					count.set(north, count.get(north) + 1);
				}
				else if (north == 0) {
					label[i][j] = west;
					count.set(west, count.get(west) + 1);
				}
				else {
					int min = Math.min(north, west);
					label[i][j] = min;
					count.set(min, count.get(min) + 1);
					if (north != west) {
						int x = findSet(sets, north);
						int y = findSet(sets, west);
						if (x != y) {
							sets.get(x).addAll(sets.get(y));
							sets.remove(y);
						}
					}
				}
			}
		}
		
		int max = 0;
		for (HashSet<Integer> set : sets) {
			int size = 0;
			for (int x : set) {
				size += count.get(x);
			}
			if (size > max) max = size;
		}
		
		return max;
	}
	
	private int findSet(ArrayList<HashSet> sets, int x) {
		for (int i=0; i<sets.size(); i++) {
			if (sets.get(i).contains(x)) return i;
		}
		return -1;
	}
}
